\begin{appendix}

\begin{center}
{\Large APPENDIX}
\end{center}
\section{Proofs from Section~\ref{sec:sp-dags}}
\noindent  Proof of Lemma~\ref{lemma:sp1.1}:

By induction on the structure of $G$.

\textbf{Base}: in an SP-DAG with a single multi-edge, $P$ is a single
edge from $Z$ to $W$.  $Z$ trivially dominates itself.

\textbf{Ind.}: Otherwise, $G$ is either $\Sc(H_1,H_2)$ or $\Pc(H_1,H_2)$
for SP-DAGs $H_1$, $H_2$.  If $Z$ is the source of $G$, then $Z$
trivially dominates all of $G$, since SP-DAGs have a single source.
$Z$ can not be the sink of $G$ since the sink has no outgoing edges.

Now $Z$ lies either in $H_1 - H_2$ or in $H_2 - H_1$, or $G = \Sc(H_1,
H_2)$ and $Z$ is the sink of $H_1$ and the source of $H_2$.  If $Z$ is
in $H_1 - H_2$, then $H_1$'s sink always postdominates $Z$, so $W$,
the immediate postdominator of $Z$, is a node in $H_1$.  Applying the
IH to subgraph $H_1$, the Lemma holds for $Z$ and $W$.  Analogous
reasoning holds if $Z$ is in $H_2 - H_1$.  Finally, if $Z$ is the
source of $H_2$ and the sink of $H_1$, then $W$ is in $H_2$ and $Z$
dominates all of $H_2$.
\qed

\noindent Proof of Lemma~\ref{lemma:sp1.2}:

  Suppose not.  WLOG, let the counterexample simple cycle $C$ leave
  $Z$ via edge $e = Z\to U$ and return via edge $e' = Z\to V$.  Since
  $C$ passes through an edge in $H_2$, it must also pass through both
  $X$ and $Y$, since those are the only two nodes that connect $H_1$
  and $H_2$.  So there must be two vertex-disjoint undirected paths in
  $H_1$: $P_1$ goes from $Z$ to $U$ to $Y$, and $P_2$ (entirely in
  $H_1$) goes from $Z$ to $V$ to $X$.

  Let $W$ be the immediate postdominator of $Z$, which lies in
  $H_1$. We claim that both paths $P_1$ and $P_2$ must pass through
  $W$.

  Suppose path $P_1$ does not pass through $W$.  Now $U$ is a
  predecessor of $W$, while $Y$ is not, so there is some first edge in
  $P_1$ that connects a predecessor $A$ of $W$ to a non-predecessor
  $B$.  We have two cases.
\begin{enumerate}
\item If the edge is oriented $A \to B$, then there is a directed
path from $Z$ to $A$ to $B$ to $Y$ that bypasses $W$, which
contradicts $W$'s postdomination of $Z$.
\item If the edge is oriented $B \to A$, then $B$ is not a successor
of $W$, since $G$ is acyclic. There is then a directed path from $X$
to $B$ to $A$ that bypasses $Z$, which contracts $Z$'s domination of
$A$ by Lemma~\ref{lemma:sp1.1}.
\end{enumerate}
Conclude that $P_1$ must indeed pass through $W$.

Suppose $P_2$ doesn't pass through $W$.  Now $V$ is a successor of
$Z$, while $X$ is not; hence, there is some first edge on path $P_2$
that connects a successor $A$ of $Z$ to a non-successor $B$.  This
edge must be oriented $B\to A$, else $B$ would be a successor of $Z$.

Now $A$ cannot be a predecessor of $W$; otherwise, there would be a
directed path from $X$ to $B$ to $A$ that bypasses $Z$, contradicting
$Z$'s dominance of $A$ by Lemma~\ref{lemma:sp1.1}. Hence, $A$ is a
successor of $W$.  The subpath of $P_2$ from $V$ to $A$ therefore
contains some first edge connecting a predecessor $C$ of $W$ to a
successor $D$ of $W$.  This edge must be oriented $C\to D$, since $G$
is acyclic. But then there is a directed path from $Z$ to $C$ to $D$
to $Y$ that bypasses $W$, which contradicts $W$'s postdomination of
$Z$.  Conclude that $P_2$ must indeed pass through $W$.

Since $P_1$ and $P_2$ both contain $W$, they are not vertex disjoint,
leading us to a contradiction.
\qed


\noindent Proof of Lemma~\ref{lem:sp1.3}:

  We know from Lemma~\ref{lemma:sp1.2} that undirected simple
  cycles in $G$ that traverse edges of both $H_1$ and $H_2$ do not
  pass through two outgoing edges of any node other than $X$.
  Moreover, each such cycle passes through two incoming edges of node
  $Y$, since $Y$ does not have any outgoing edges.

  Let $P_1$ be the directed path on $C$ that exits $X$ in (WLOG)
  $H_1$. If this path were to terminate at some node $Z$ prior to $Y$,
  then the portion of cycle following $P_1$ would traverse two
  adjacent incoming edges of $Z$.  But if the cycle leaves $Z$ via an
  edge that points into $Z$ and eventually reaches $Y$ via an edge
  that points into $Y$, it must at some point ``change direction'' by
  passing through two outgoing edges of a node $Q$ other than $X$,
  which is impossible by Lemma~\ref{lemma:sp1.2}.

  Conclude that $C$ must be fully directed from $X$ to $Y$ in both
  components.
\qed




\noindent Proof for Lemma~\ref{lemma:spdag-cs4}:  

By induction on the structure of $G$.

\textbf{Base:} Trivially true for a single multi-edge.

\textbf{Ind.:} If $G = \Sc(H_1,H_2)$, then the property holds for
$H_1$ and $H_2$, and their serial composition creates no new cycles.
Hence the property holds for every cycle of $G$.

If $G = \Pc(H_1,H_2)$, then every new cycle created by their parallel
composition connects the common source $X$ of $G$ to its common sink
$Y$ by directed paths passing through $H_1$ and $H_2$, respectively.
All such cycles therefore have one source $X$ and one sink $Y$.
\qed




\section{Proofs from Section~\ref{sec:cs4}}

\noindent Proof for Lemma~\ref{lem:cs4K4}:

  Suppose $G$ has a subgraph $H$ homeomorphic to $K_4$.  $H$ has $4$
  ``corner'' vertices and $6$ connections (which may in general be paths
  rather than single edges) connecting them in the pattern of
  $K_4$. There are therefore $12$ incidences of connections on corner
  vertices in $H$. WLOG, suppose that at least $6$ of these are
  incoming.  Now we have two cases.
\begin{enumerate}
\item Two vertices $X$ and $Y$ of $H$ have exactly two incoming
  edges apiece.
\item One vertex has 3 incoming edges.
\end{enumerate}
Consider case 1.  If the (unique) shared connection between $X$ and
$Y$ is oriented identically w/r to $X$ and $Y$ (either into both or
out of both), then it is possible to find a cycle through $X$ and $Y$
with two sinks.  Now consider the case when the connection $X-Y$ is
directed out of one vertex and into the other.  Suppose WLOG that
connection $x-y$ is directed out of $X$ and into $Y$. Let $W$ and $Z$
be the other two corner vertices of $H$.

Exactly one of the connections $Y-W$ and $Y-Z$ must be directed out of
$Y$.  Suppose WLOG that $Y-Z$ is directed out of $Y$.  Because each of
$X$ and $Y$ have exactly two incoming edges, we know the following:
(1) $X-Z$ must be directed into $X$; (2) $W-X$ must be directed into
$X$; (3) $W-Y$ must be directed into $Y$.  Now $Y-Z$ must be directed
into $Z$; otherwise, there must be a sink on this connection, and the
cycle $XWYZ$ would contain two sinks.  It follows that $X-Z$ is
directed out of $Z$; otherwise, $X$ and $Z$ would constitute the
forbidden case (1).

Now we established above that $Y-Z$ may not contain a sink. Similarly,
$X-Z$ may not contain a sink because of cycle $XWZ$, and $X-Y$ may not
contain a sink because of cycle $XWY$.  Hence, cycle $XYZ$ must be a
directed cycle, which is forbidden because $G$ is a DAG.

Consider case 2 above, where one corner vertex $v$ of $H$ has three
incoming edges.  Then no other corner vertex of $H$ can have two
incoming edges without creating a cycle with two sinks. Since $H$ has
at least six incoming edges on its corner vertices, it follows that
the other three corner vertices of $H$ each have exactly one incoming,
and hence two outgoing, edges.  Repeat the argument of Case (1) for
any two of these vertices, swapping ``in'' and ``out''.

Conclude that there is no way to direct the edges of $H$ so as to ensure
that all its cycles have one source and one sink.  
\qed


\begin{corollary}
Every CS4 graph is planar.
\end{corollary}
\begin{proof}
If $G$ contains no subgraph homeomorphic to $K_4$, then it contains no
subgraph homeomorphic to either $K_5$ or $K_{3,3}$, both of which contain
subgraphs homeomorphic to $K_4$.  By Kuratowski's Theorem, $G$ must be
planar.
\end{proof}

\noindent Proof of Lemma~\ref{lem:cs4ChordTraverse}:

  $C$ reaches an internal vertex of $H$ from outside, so it must
  consist of a simple path $P$ in $H$ that connects $u$ to $v$, plus a
  path to return from $v$ to $u$ outside $H$.  We claim that path $P$
  is directed. Suppose not; $P$ enters and leaves $H$ through edges
  directed out of its source and into its sink, so $P$ must contain an
  internal source at some node $Z$.  But Lemma~\ref{lemma:sp1.2}
  showed that there is no simple path connecting the source and sink
  of $H$ that contains an internal source.
\qed


\noindent Proof of Lemma~\ref{lem:cs4-cycle}:

By induction on $k$.

\textbf{Base:} Trivially true if $k = 0$; set $C' = C$.

\textbf{Ind.:} Suppose that $C$ traverses $k$ cross-links of $G$.
Order these links as $H_1\ldots H_k$ in topologically increasing order
of their endpoints (which is possible, because they cannot cross).
Let $u_i < v_i$ be the endpoints of $H_i$ in $G$.

We claim that either $C$ does not pass through any strict predecessor
of $u_1$ or $v_1$, or that it does not pass through any strict
successor of $u_k$ or $v_k$.  Since $C$ traverses $H_1$, it contains a
directed path from $u_1$ to $v_1$.  Starting from $v_1$, $C$ must
return by some undirected path $P$ to $u_1$. Now if the first edge on
this path touches a predecessor of $v_1$, then $C$ must return to
$u_1$ without touching any successor w of $u_1$ or $v_1$; indeed, to
reach w without passing through $u_1$ or $v_1$ itself, the path would
have to traverse a chord graph that crosses $H_1$, which cannot exist.
If, on the other hand, $P$'s first edge touches a successor of $v_1$,
then $C$ must return to $u_1$ without touching any predecessor $w$ of
$u_1$ or $v_1$, for the same reason.

Suppose that $C$ does not touch a predecessor of $u_1$ or
$v_1$. Construct $C'$ from $C$ by removing the path through $H_1$ and
replacing it with the path on $G$'s outer cycle that connects $u_1$
and $v_1$, passing through $G$'s source $X$.  $C'$ does not contain
the source that lies at endpoint $u_1$ of $H_1$ in $C$, but it does
contain a new source at $X$.  Removing $H_1$ cannot eliminate any
other source or sink of $C$, so $C'$ has as many sources/sinks as $C$.

If instead $C$ does not touch a successor of $u_k$ or $v_k$, construct
$C'$ from $C$ by removing the path through $H_k$ and replacing it with
the path on $G$'s outer cycle that directly connects $u_k$ and $v_k$,
passing through G's sink $Y$.  $C'$ does not contain the sink that
lies at endpoint $v_k$ of $H_k$ in $C$, but it does contain a new sink
at $Y$.  Removing $H_k$ cannot eliminate any other source or sink of
$C$, so $C'$ has as many sources/sinks as $C$.

By the IH, there is a cycle $C''$ in $G$ with at least as many
sources/sinks as $C'$ that does not pass through any cross-link of
$G$.
\qed

\section{Proofs from Section~\ref{sec:sp-ladder-dummy}}

\noindent Proof of Lemma~\ref{lem:spladder-prop}:

  From the For claim 1, if a source forwards a dummy message, it is an
  external dummy message, and therefore its sink must be a corner
  node, and it must traverse the entire chord graph on which it is
  forwarded.  In addition, when a corner source gets a dummy message
  not intended for itself, it forwards it along all its edges.
  Therefore, it must go through all the nodes of the chord graph
  before it reaches the sink.

  Claims 2 and 3 are true due to Lemma~\ref{fact:ladderCycleProp}.
\qed

\noindent Proof of Lemma~\ref{lem:spladder-maxint}:

  Consider a span of $\tau_i$ consecutive messges received by $X$.
  Before these messages arrive, $c_i$ has some value $< \tau_i$.  For
  each incoming message, one of the following will occur.
\begin{enumerate}
\item The counter will be incremented until it reaches $\tau_i$, triggering a
  dummy message to $d_i$.
\item The counter will be zeroed out because some other dummy message
  is sent or forwarded.  
  From node behavior and Lemma~\ref{lem:spladder-prop}, the counter is
  zeroed out only if the dummy message sent or forwarded will pass
  through $d_i$.
\end{enumerate}
\qed

\noindent Proof of Lemma~\ref{lem:intervals}:

  Using the above procedure for setting intervals, to start with,
  every cross-link edge will have a dummy interval with $p_a =
  (L_K(u_i, t), t)$ set.  If the dummy interval was later removed, it
  is because another dummy pair $p_b$ causes a dummy message with the
  same or higher frequency to be sent, and this dummy message will
  traverse all the paths that a dummy message due to $p_b$ would take.

Therefore, by Lemma~\ref{lem:spladder-maxint} implies the proof.  
\qed




\end{appendix}
